//https://leetcode.cn/problems/sum-lists-lcci/
class Solution {
    public:
    ListNode* addTwoNumbers(ListNode* list1, ListNode* list2) {
        if(!list1 && !list2) return nullptr;
        //如果其中一条链表尾空,那么就返回另外一条链表
        if(!list1) return list2;
        if(!list2) return list1; 

        ListNode* phead  = new ListNode(-1);
        ListNode* tail = phead;

        int carry = 0;//进位
        while(list1|| list2 || carry) //其中一条链表没有遍历完 || 进位不为0,都继续操作
        {
            int sum = 0;//当前计算节点相加的值,注意:每次都需要重新将sum置为0！！否则还是上次计算的值
            if(list1 != nullptr)
            {
                sum += list1->val,list1 = list1->next;
            }
            if(list2 != nullptr) 
            {
                sum += list2->val,list2 = list2->next;
            }

            sum += carry;//注意要加上进位值
            carry = sum / 10; //坑点：carry的计算要放在sum取模之前，否则每次carry的值都是0
            sum = sum % 10;

            ListNode* newNode = new ListNode(sum);
            tail -> next = newNode;
            tail = tail->next;
        }
        return phead->next;
    }
};

//https://www.nowcoder.com/practice/c56f6c70fb3f4849bc56e33ff2a50b6b?tpId=295&tqId=1008772&ru=/exam/company&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Fcompany
class Solution {
public:
    ListNode* ReverseList(ListNode* head) //返回逆置之后的链表的头
    {
        ListNode* cur = head,*prev = nullptr,*next = nullptr;
        while(cur)
        {
            //prev cur next
            next = cur->next;
            cur->next = prev;
            //迭代往后走
            prev = cur;
            cur = next;
        }
        return prev;
    }
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        if(!head1 && !head2) return nullptr;
        //如果其中一条链表为空,那么返回另外一条链表
        if(!head1) return head2;
        if(!head2) return head1;

        //逆置两条链表
        head1 = ReverseList(head1);
        head2 = ReverseList(head2);
        //正序求和
        ListNode* phead = new ListNode(-1);
        ListNode* tail = phead;
        int carry = 0;
        while(head1 || head2 || carry)
        {
            int sum = 0;
            if(head1) sum += head1->val,head1 = head1->next;
            if(head2) sum += head2->val,head2 = head2->next;
            sum += carry;

            carry = sum / 10;
            sum = sum % 10;
            tail->next = new ListNode(sum);
            tail = tail->next;
        }
        //逆置结果链表
        return ReverseList(phead->next);
    }
};

//https://leetcode.cn/problems/odd-even-linked-list/

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(!head || !head->next) return head;
        ListNode* EvenList = new ListNode(-1);//偶数位置链表
        ListNode* OddList = new ListNode(-1);//奇数位置链表
        //遍历原链表,将节点尾插到对应的链表
        ListNode* EvenTail = EvenList; 
        ListNode* OddTail = OddList;
        ListNode* cur = head;
        int count = 1;//第一个节点是奇数
        while(cur)
        {
            //将当前节点独立
            ListNode* next = cur->next;
            cur->next  = nullptr;
            if(count % 2) //奇数
            {
                OddTail->next = cur;
                OddTail = OddTail->next;
            }
            else 
            {
                EvenTail->next = cur;
                EvenTail = EvenTail->next;
            }
            count++;
            cur = next;
        }
        OddTail->next = EvenList->next;
        return OddList->next;
    }   
};

//https://leetcode.cn/problems/sort-list/

class Solution {
    public:
    //分割两段链表 ==>找链表的中间节点的上一个
    ListNode* splitList(ListNode* head)
    {
        if(!head || !head->next)     return head;
        ListNode* fast = head;
        ListNode* slow = head;
        ListNode* prev = head;
        while(fast&&fast->next)
        {
            prev = slow;
            fast = fast->next->next;
            slow = slow->next;
        }
        return prev;
    }
    //合并两条有序链表
    ListNode* MergeSort(ListNode* head1,ListNode* head2)
    {
        ListNode* dummy = new ListNode(-1);
        ListNode* tail = dummy;
        while(head1 && head2)
        {
            if(head1->val < head2->val)
            {
                tail->next = head1;
                tail = head1;
                head1 = head1->next;
            }
            else
            {
                tail->next = head2;
                tail = head2;
                head2 = head2->next;
            }
        }
        if(head1)   tail->next = head1;
        if(head2)   tail->next = head2;

        return dummy->next;
    }
    ListNode* sortList(ListNode* head) {
        if(!head || !head->next)    return head;
        ListNode* mid = splitList(head);
        ListNode* midNext = mid->next;
        mid->next = nullptr;
        //[head,mid] [mid->next,....]
        ListNode* head1 = sortList(head);
        ListNode* head2 = sortList(midNext);
        return MergeSort(head1,head2);
    }
};

//https://leetcode.cn/problems/delete-node-in-a-linked-list/description/

class Solution {
public:
    void deleteNode(ListNode* node) {
        //链表为空 || 尾节点
        if(!node  || !node->next) return ;
        ListNode* nodeNext = node->next;
        node->val = nodeNext->val;
        node->next = nodeNext->next;
        delete nodeNext;
    }
};